{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Parse Lisp Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evaluate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #Lisp 语法解析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个类似 Lisp 语句的字符串表达式 <code>expression</code>，求出其计算结果。</p>\n",
    "\n",
    "<p>表达式语法如下所示:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>表达式可以为整数，<strong>let</strong> 表达式，<strong>add</strong> 表达式，<strong>mult</strong> 表达式，或赋值的变量。表达式的结果总是一个整数。</li>\n",
    "\t<li>(整数可以是正整数、负整数、0)</li>\n",
    "\t<li><strong>let</strong> 表达式采用&nbsp;<code>\"(let v<sub>1</sub> e<sub>1</sub> v<sub>2</sub> e<sub>2</sub> ... v<sub>n</sub> e<sub>n</sub> expr)\"</code> 的形式，其中&nbsp;<code>let</code> 总是以字符串&nbsp;<code>\"let\"</code>来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量&nbsp;<code>v<sub>1</sub></code>被分配为表达式&nbsp;<code>e<sub>1</sub></code>&nbsp;的值，第二个变量&nbsp;<code>v<sub>2</sub></code>&nbsp;被分配为表达式&nbsp;<code>e<sub>2</sub></code>&nbsp;的值，<strong>依次类推</strong>；最终 <code>let</code> 表达式的值为&nbsp;<code>expr</code>表达式的值。</li>\n",
    "\t<li><strong>add </strong>表达式表示为&nbsp;<code>\"(add e<sub>1</sub> e<sub>2</sub>)\"</code> ，其中&nbsp;<code>add</code> 总是以字符串&nbsp;<code>\"add\"</code> 来表示，该表达式总是包含两个表达式 <code>e<sub>1</sub></code>、<code>e<sub>2</sub></code> ，最终结果是&nbsp;<code>e<sub>1</sub></code> 表达式的值与&nbsp;<code>e<sub>2</sub></code>&nbsp;表达式的值之 <strong>和 </strong>。</li>\n",
    "\t<li><strong>mult</strong> 表达式表示为&nbsp;<code>\"(mult e<sub>1</sub> e<sub>2</sub>)\"</code>&nbsp;，其中&nbsp;<code>mult</code> 总是以字符串 <code>\"mult\"</code> 表示，该表达式总是包含两个表达式 <code>e<sub>1</sub></code>、<code>e<sub>2</sub></code>，最终结果是&nbsp;<code>e<sub>1</sub></code> 表达式的值与&nbsp;<code>e<sub>2</sub></code>&nbsp;表达式的值之<strong> 积 </strong>。</li>\n",
    "\t<li>在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，<code>\"add\"</code> ，<code>\"let\"</code> ，<code>\"mult\"</code> 会被定义为 \"关键字\" ，不会用作变量名。</li>\n",
    "\t<li>最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。</li>\n",
    "</ul>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"(let x 2 (mult x (let x 3 y 4 (add x y))))\"\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>\n",
    "计算表达式 (add x y), 在检查变量 x 值时，\n",
    "在变量的上下文中由最内层作用域依次向外检查。\n",
    "首先找到 x = 3, 所以此处的 x 值是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"(let x 3 x 2 x)\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>let 语句中的赋值运算按顺序处理即可。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"(let x 1 y 2 x (add x y) (add x y))\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。 \n",
    "第二个 (add x y) 计算结果是 3 + 2 = 5 。\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 2000</code></li>\n",
    "\t<li><code>exprssion</code> 中不含前导和尾随空格</li>\n",
    "\t<li><code>expressoin</code> 中的不同部分（token）之间用单个空格进行分隔</li>\n",
    "\t<li>答案和所有中间计算结果都符合 <strong>32-bit</strong> 整数范围</li>\n",
    "\t<li>测试用例中的表达式均为合法的且最终结果为整数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [parse-lisp-expression](https://leetcode.cn/problems/parse-lisp-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [parse-lisp-expression](https://leetcode.cn/problems/parse-lisp-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(let x 2 (mult x (let x 3 y 4 (add x y))))\"', '\"(let x 3 x 2 x)\"', '\"(let x 1 y 2 x (add x y) (add x y))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        i, n = 0, len(expression)\n",
    "\n",
    "        def parseVar() -> str:\n",
    "            nonlocal i\n",
    "            i0 = i\n",
    "            while i < n and expression[i] != \" \" and expression[i] != \")\":\n",
    "                i += 1\n",
    "            return expression[i0:i]\n",
    "\n",
    "        def parseInt() -> int:\n",
    "            nonlocal i\n",
    "            sign, x = 1, 0\n",
    "            if expression[i] == \"-\":\n",
    "                sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x = x * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            return sign * x\n",
    "\n",
    "        scope = defaultdict(list)\n",
    "\n",
    "        def innerEvaluate() -> int:\n",
    "            nonlocal i\n",
    "            if expression[i] != \"(\":\n",
    "                if expression[i].islower():\n",
    "                    return scope[parseVar()][-1]\n",
    "                return parseInt()\n",
    "            i += 1\n",
    "            if expression[i] == \"l\":\n",
    "                i += 4\n",
    "                vars = []\n",
    "                while True:\n",
    "                    if not expression[i].islower():\n",
    "                        ret = innerEvaluate()\n",
    "                        break\n",
    "                    var = parseVar()\n",
    "                    if expression[i] == \")\":\n",
    "                        ret = scope[var][-1]\n",
    "                        break\n",
    "                    vars.append(var)\n",
    "                    i += 1\n",
    "                    scope[var].append(innerEvaluate())\n",
    "                    i += 1\n",
    "                for var in vars:\n",
    "                    scope[var].pop()\n",
    "            elif expression[i] == \"a\":\n",
    "                i += 4\n",
    "                e1 = innerEvaluate()\n",
    "                i += 1\n",
    "                e2 = innerEvaluate()\n",
    "                ret = e1 + e2\n",
    "            else:\n",
    "                i += 5\n",
    "                e1 = innerEvaluate()\n",
    "                i += 1\n",
    "                e2 = innerEvaluate()\n",
    "                ret = e1 * e2\n",
    "            i += 1\n",
    "            return ret\n",
    "\n",
    "        return innerEvaluate()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos == len(expression)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        stacks = []\n",
    "        maps = []\n",
    "\n",
    "        def parseValue(v, map):\n",
    "            if type(v) is int or v[0] == \"-\" or v.isnumeric():\n",
    "                # 整数, 注意负数\n",
    "                return int(v)\n",
    "            elif v in map:\n",
    "                # 返回映射值\n",
    "                return map[v]\n",
    "            else:\n",
    "                # 返回原值\n",
    "                return v\n",
    "\n",
    "        def addValue(v, stack, map):\n",
    "            op = stack[0]\n",
    "            if op == \"let\" and len(stack) & 1:\n",
    "                # 注意奇数长度let栈不解析!!!\n",
    "                stack.append(v)\n",
    "            else:\n",
    "                v = parseValue(v, map)\n",
    "                if op == \"let\":\n",
    "                    # let的话需要额外更新map\n",
    "                    map[stack[-1]] = v\n",
    "                stack.append(v)\n",
    "\n",
    "        def calResult(stack, map):\n",
    "            # 计算当前栈的结果\n",
    "            op = stack[0]\n",
    "            if op == \"let\":\n",
    "                return parseValue(stack[-1], map)\n",
    "            elif op == \"add\":\n",
    "                return parseValue(stack[-2], map) + parseValue(stack[-1], map)\n",
    "            else:\n",
    "                return parseValue(stack[-2], map) * parseValue(stack[-1], map)\n",
    "\n",
    "        for w in expression.split():\n",
    "            if w[0] == \"(\":\n",
    "                op = w[1:]\n",
    "                stacks.append([op])\n",
    "                # 复制上一层的map\n",
    "                nmap = maps[-1].copy() if maps else {}\n",
    "                maps.append(nmap)\n",
    "            elif w[-1] == \")\":\n",
    "                # 先将当前值加入最新一层的栈中\n",
    "                v = w[: w.find(\")\")]\n",
    "                addValue(v, stacks[-1], maps[-1])\n",
    "                # 每有一个右括号就弹出一层\n",
    "                for i in range(len(w))[::-1]:\n",
    "                    if w[i] != \")\":\n",
    "                        break\n",
    "                    res = calResult(stacks.pop(), maps.pop())\n",
    "                    if stacks:\n",
    "                        # 将该层栈计算的结果加入前一层栈\n",
    "                        addValue(res, stacks[-1], maps[-1])\n",
    "                    else:\n",
    "                        # 最后一个右括号, 得到的结果即为最终结果~\n",
    "                        return res\n",
    "            else:\n",
    "                # 正常表达式,addValue之\n",
    "                addValue(w, stacks[-1], maps[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos == len(expression)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos == len(expression)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, e: str) -> int:\n",
    "        i, n = 0, len(e)\n",
    "        scope = defaultdict(list)\n",
    "\n",
    "        def parVar():\n",
    "            nonlocal i\n",
    "            left = i\n",
    "            while i< n and e[i] != ' ' and e[i] != ')':\n",
    "                i += 1\n",
    "            return e[left:i]\n",
    "        def parInt():\n",
    "            nonlocal i\n",
    "            flag = 1\n",
    "            x = 0\n",
    "            if e[i] == '-':\n",
    "                flag = -1\n",
    "                i += 1\n",
    "            while i<n and e[i].isdigit():\n",
    "                x = x * 10 + int(e[i])\n",
    "                i += 1\n",
    "            return x * flag\n",
    "        \n",
    "        def helper():\n",
    "            nonlocal i\n",
    "            if e[i] != '(':\n",
    "                if e[i].islower():\n",
    "                    return scope[parVar()][-1]\n",
    "                return parInt()\n",
    "            i += 1\n",
    "            if e[i] == 'l':\n",
    "                i += 4\n",
    "                vars = []\n",
    "                while True:\n",
    "                    if not e[i].islower():\n",
    "                        ret = helper()\n",
    "                        break\n",
    "                    var = parVar()\n",
    "                    if e[i] == ')':\n",
    "                        ret = scope[var][-1]\n",
    "                        break\n",
    "\n",
    "                    vars.append(var)\n",
    "\n",
    "                    i += 1\n",
    "                    scope[var].append(helper())\n",
    "                    i += 1\n",
    "                for var in vars:\n",
    "                    scope[var].pop()\n",
    "            elif e[i] == 'a':  # \"add\" 表达式\n",
    "                i += 4  # 移除 \"add \"\n",
    "                e1 = helper()\n",
    "                i += 1  # 移除空格\n",
    "                e2 = helper()\n",
    "                ret = e1 + e2\n",
    "            else:  # \"mult\" 表达式\n",
    "                i += 5  # 移除 \"mult \"\n",
    "                e1 = helper()\n",
    "                i += 1  # 移除空格\n",
    "                e2 = helper()\n",
    "                ret = e1 * e2\n",
    "            i += 1  # 移除右括号\n",
    "            return ret\n",
    "\n",
    "        return helper()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        def f(expr, vals):\n",
    "            if expr[0]=='(':\n",
    "                return f(expr[1:-1], vals)\n",
    "            ind = expr.find(' ')\n",
    "            if ind == -1:\n",
    "                if expr.isdigit() or expr.startswith('-') and expr[1:].isdigit():\n",
    "                    return int(expr)\n",
    "                for i in range(len(vals)-1, -1, -1):\n",
    "                    if expr in vals[i]:\n",
    "                        return vals[i][expr]\n",
    "            ops = expr[:ind]\n",
    "            nums = []\n",
    "            p, q = ind+1, ind+2\n",
    "            while p<len(expr):\n",
    "                if expr[p]=='(':\n",
    "                    tmp = 1\n",
    "                    while tmp>0:\n",
    "                        if expr[q] == '(':\n",
    "                            tmp += 1\n",
    "                        elif expr[q] == ')':\n",
    "                            tmp -=1\n",
    "                        q+=1\n",
    "                else:\n",
    "                    while q<len(expr) and expr[q]!=' ':\n",
    "                        q+=1\n",
    "                nums.append(expr[p:q])\n",
    "                p = q+1\n",
    "                q = p+1\n",
    "            if ops == 'add':\n",
    "                return f(nums[0], vals)+f(nums[1], vals)\n",
    "            if ops == 'mult':\n",
    "                return f(nums[0], vals)*f(nums[1], vals)\n",
    "            vals.append({})\n",
    "            for i in range(0, len(nums)-2, 2):\n",
    "                vals[-1][nums[i]] = f(nums[i+1], vals)\n",
    "            ans = f(nums[-1], vals)\n",
    "            del(vals[-1])\n",
    "            return ans\n",
    "        return f(expression, [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos == len(expression)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_lst(s, pos):\n",
    "    lst = []\n",
    "    while True:\n",
    "        v, pos = get_one_item(s, pos)\n",
    "        lst.append(v)\n",
    "        if s[pos] == ')':\n",
    "            break\n",
    "        assert s[pos] == ' '\n",
    "        pos += 1\n",
    "    return lst, pos\n",
    "\n",
    "\n",
    "def get_one_item(s, pos):\n",
    "    s0 = ''\n",
    "    if s[pos] == '(':\n",
    "        savpos = pos\n",
    "        lst, pos = get_lst(s, pos + 1)\n",
    "        assert s[pos] == ')'\n",
    "        pos += 1\n",
    "        return s[savpos:pos], pos\n",
    "\n",
    "    while True:\n",
    "        c = s[pos]\n",
    "        if c in ' )':\n",
    "            break\n",
    "        s0 += c\n",
    "        pos += 1\n",
    "    return s0, pos\n",
    "\n",
    "\n",
    "def lookup_var(s_var, lstdic):\n",
    "    for dic in lstdic:\n",
    "        if s_var in dic:\n",
    "            return dic[s_var]\n",
    "    assert False\n",
    "\n",
    "def is_number(s_item):\n",
    "    return s_item[0] in '0123456789-'\n",
    "\n",
    "\n",
    "def get_value(s_item, lstdic):\n",
    "    if s_item[0] == '(':\n",
    "        num, _ = handle_value(s_item, 0, lstdic)\n",
    "        return num\n",
    "    if is_number(s_item):\n",
    "        num = int(s_item)\n",
    "        return num\n",
    "    num = lookup_var(s_item, lstdic)\n",
    "    return num\n",
    "\n",
    "\n",
    "def handle_value(s, pos, lstdic):\n",
    "    if s[pos] != '(':\n",
    "        s_item, pos = get_one_item(s, pos)\n",
    "        num = get_value(s_item, lstdic)\n",
    "        return num, pos\n",
    "    lst, pos = get_lst(s, pos + 1)\n",
    "\n",
    "    assert s[pos] == ')'\n",
    "    pos += 1\n",
    "\n",
    "    if lst[0] == 'let':\n",
    "        dic = {}\n",
    "        assert len(lst) % 2 == 0\n",
    "        i = 1\n",
    "        while i < len(lst) - 1:\n",
    "            s1 = lst[i]\n",
    "            s2 = lst[i + 1]\n",
    "            value = get_value(s2, [dic] + lstdic)\n",
    "            dic[s1] = value\n",
    "            i += 2\n",
    "        s = lst[-1]\n",
    "        value = get_value(s, [dic] + lstdic)\n",
    "        return value, pos\n",
    "    elif lst[0] == 'add':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 + v2, pos\n",
    "    elif lst[0] == 'mult':\n",
    "        assert len(lst) == 3\n",
    "        v1 = get_value(lst[1], lstdic)\n",
    "        v2 = get_value(lst[2], lstdic)\n",
    "        return v1 * v2, pos\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, expression: str) -> int:\n",
    "        value, pos = handle_value(expression, 0, [])\n",
    "        assert pos\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def evaluate(self, expression: str) -> int:\r\n",
    "        global_vals={}\r\n",
    "\r\n",
    "        # L=len(expression)\r\n",
    "        idx=0\r\n",
    "\r\n",
    "        def parse_var_name():\r\n",
    "            nonlocal idx\r\n",
    "            start=idx\r\n",
    "            while expression[idx]!=' ' and expression[idx]!=')':\r\n",
    "                idx+=1\r\n",
    "            return expression[start:idx]\r\n",
    "\r\n",
    "        def parse_val():\r\n",
    "            nonlocal idx\r\n",
    "            sign=1\r\n",
    "            if expression[idx]=='-':\r\n",
    "                sign=-1\r\n",
    "                idx+=1\r\n",
    "            num=0\r\n",
    "            while expression[idx]!=' ' and expression[idx]!=')':\r\n",
    "                num=num*10+ord(expression[idx])-ord('0')\r\n",
    "                idx+=1\r\n",
    "            return num*sign\r\n",
    "        \r\n",
    "        def parse_let():\r\n",
    "            nonlocal idx\r\n",
    "            # var_name=''\r\n",
    "            ret=None\r\n",
    "            vars=[]\r\n",
    "            while True:\r\n",
    "                if expression[idx].islower()==False:\r\n",
    "                    ret=parse()\r\n",
    "                    break\r\n",
    "\r\n",
    "                var_name=parse_var_name()\r\n",
    "                if expression[idx]==')':\r\n",
    "                    ret=global_vals[var_name][-1]\r\n",
    "                    break\r\n",
    "\r\n",
    "                idx+=1\r\n",
    "                \r\n",
    "                global_vals.setdefault(var_name,[]).append(parse())\r\n",
    "                vars.append(var_name)\r\n",
    "                idx+=1\r\n",
    "            for var in vars:\r\n",
    "                global_vals[var].pop()\r\n",
    "            return ret\r\n",
    "                \r\n",
    "        \r\n",
    "        Add=lambda x,y:x+y\r\n",
    "        Mul=lambda x,y:x*y\r\n",
    "        def parse_calc(operator):\r\n",
    "            nonlocal idx\r\n",
    "            val1=parse()\r\n",
    "            idx+=1\r\n",
    "            val2=parse()\r\n",
    "            \r\n",
    "            return operator(val1,val2)\r\n",
    "\r\n",
    "\r\n",
    "                    \r\n",
    "        def parse():\r\n",
    "            nonlocal idx\r\n",
    "            if expression[idx]!='(':\r\n",
    "                if expression[idx].islower():\r\n",
    "                    return global_vals[parse_var_name()][-1]\r\n",
    "                return parse_val()\r\n",
    "            idx+=1\r\n",
    "            if expression[idx]=='l':\r\n",
    "                idx+=4\r\n",
    "                ret= parse_let()\r\n",
    "            elif expression[idx]=='a':\r\n",
    "                idx+=4\r\n",
    "                ret= parse_calc(Add)\r\n",
    "            else:\r\n",
    "                idx+=5\r\n",
    "                ret= parse_calc(Mul)\r\n",
    "            idx+=1\r\n",
    "            return ret\r\n",
    "        \r\n",
    "        return parse()\r\n",
    "                \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def evaluate(self, expression: str) -> int:\r\n",
    "        fields=[{}]\r\n",
    "        # segmengs=expression.split(' ')\r\n",
    "        # L=len(segmengs)\r\n",
    "        L=len(expression)\r\n",
    "        idx=0\r\n",
    "        # assigning_fiels=[]\r\n",
    "        # Let,Add,Mul=1,2,3\r\n",
    "        # op=-1\r\n",
    "        def parse_field_name():\r\n",
    "            nonlocal idx,L\r\n",
    "            start=idx\r\n",
    "            while idx<L and expression[idx]!=' ' and expression[idx]!=')':\r\n",
    "                idx+=1\r\n",
    "            return expression[start:idx]\r\n",
    "\r\n",
    "        def parse_val():\r\n",
    "            nonlocal idx,L\r\n",
    "            sign=1\r\n",
    "            if expression[idx]=='-':\r\n",
    "                sign=-1\r\n",
    "                idx+=1\r\n",
    "            num=0\r\n",
    "            while idx<L and expression[idx]!=' ' and expression[idx]!=')':\r\n",
    "                num=num*10+ord(expression[idx])-ord('0')\r\n",
    "                idx+=1\r\n",
    "            return num*sign\r\n",
    "        def assign():\r\n",
    "            nonlocal idx,L\r\n",
    "            fields.append(fields[-1].copy())\r\n",
    "            cur_fields=fields[-1]\r\n",
    "            field_name=''\r\n",
    "            ret=None\r\n",
    "            while idx<L:\r\n",
    "                if expression[idx]==' ':\r\n",
    "                    idx+=1\r\n",
    "                    continue\r\n",
    "                elif expression[idx]=='(':\r\n",
    "                    idx+=1\r\n",
    "                    val=parse()\r\n",
    "                    if field_name:\r\n",
    "                        cur_fields[field_name]=val\r\n",
    "                        field_name=''\r\n",
    "                    else:\r\n",
    "                        ret=val\r\n",
    "                elif expression[idx]==')':\r\n",
    "                    idx+=1\r\n",
    "                    fields.pop()\r\n",
    "                    return cur_fields[field_name] if field_name else ret\r\n",
    "                elif expression[idx].isalpha():\r\n",
    "                    name=parse_field_name()\r\n",
    "                    if field_name:\r\n",
    "                        cur_fields[field_name]=cur_fields[name]\r\n",
    "                        field_name=''\r\n",
    "                    else:\r\n",
    "                        field_name=name\r\n",
    "                else:                    \r\n",
    "                    val=parse_val()\r\n",
    "                    if not field_name:\r\n",
    "                        ret=val\r\n",
    "                    else:\r\n",
    "                        cur_fields[field_name]=val\r\n",
    "                        field_name=''\r\n",
    "        \r\n",
    "        Add=lambda x,y:x+y\r\n",
    "        Mul=lambda x,y:x*y\r\n",
    "        def calc(operator):\r\n",
    "            nonlocal idx,L\r\n",
    "            cur_fields=fields[-1]\r\n",
    "            ops=[]\r\n",
    "\r\n",
    "            while idx<L:\r\n",
    "                if expression[idx]==' ':\r\n",
    "                    idx+=1\r\n",
    "                    continue\r\n",
    "                elif expression[idx].isalpha():\r\n",
    "                    ops.append(cur_fields[parse_field_name()])\r\n",
    "                elif expression[idx].isnumeric() or expression[idx]=='-':\r\n",
    "                    ops.append(parse_val())\r\n",
    "                elif expression[idx]=='(':\r\n",
    "                    idx+=1\r\n",
    "                    ops.append(parse())\r\n",
    "                elif expression[idx]==')':\r\n",
    "                    idx+=1\r\n",
    "                    return operator(ops[0],ops[1])\r\n",
    "                else:\r\n",
    "                    idx+=1\r\n",
    "\r\n",
    "\r\n",
    "                    \r\n",
    "        def parse():\r\n",
    "            nonlocal idx,L\r\n",
    "            while idx<L:\r\n",
    "                if expression[idx]=='(' or expression[idx]==' ':\r\n",
    "                    idx+=1\r\n",
    "                    continue\r\n",
    "                # if expression[idx]==')':\r\n",
    "                #     return \r\n",
    "                op=expression[idx:idx+3]\r\n",
    "                idx+=3\r\n",
    "                if op=='let':\r\n",
    "                    return assign()\r\n",
    "                elif op=='add':\r\n",
    "                    return calc(Add)\r\n",
    "                else:\r\n",
    "                    idx+=1\r\n",
    "                    return calc(Mul)\r\n",
    "\r\n",
    "\r\n",
    "        return parse()\r\n",
    "                \r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
